#include <mips/regdef.h>


##Código obtenido "compilando" a mano el código en "C" de "tp1_heapsort.c".
##Uso solo registros temporales t0->t8 (cuando es posible) dentro del código,
##evitando usar registros callee saved, y manteniendo por tanto el stack
##lo mas simple y reducido posible. Tambien se utilizan #defines para
##poder usar los nombres de las variables originales en el codigo "C"
##para que el código sea mucho mas legible.
##Para formar el stack frame también utilizo #defines haciendo mucho
##mas simple el uso de un código genérico para cada una de las funciones
##en donde solo es necesario cambiar algunas constantes.

##Se trato de respetar la ABI, tal y como se la vió en clase, para lo cual se
##hicieron pruebas con la salida producida por el compilador para diferentes
##combinaciones de parámetros y variables locales, en estas pruebas se
##encontró que es necesario un stack distinto al mínimo necesario para poder hacer
##un debug de la función, se usó este durante el debugging.

##Las pseudoinstrucciones .ent, .frame, .cpload, .cprestore, .end son
##requeridas por GCC para la generación de código PIC (Position Independent Code).
##Debe respetarse ya que no es posible mezclar código PIC con código no PIC.

##Las pseudoinstrucciones .section, .mdebug, .abi32, .previous, .abicalls, .size
##son requeridas por GDB, para poder hacer un debbuging de la función.

##El registro gp siempre es restaurado por código automáticamente generado por el preprocesador.


##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! COMENTARIOS DEL CODIGO !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##Los comentarios siguen la convención de usar la línea de "C" correspondiente a la o las
##instrucciones de MIPS assembly, además se encierran entre corchetes comentarios que corresponden
##a una especie de pseudocódigo que utiliza los resgistros, para aclarar como se construyó la
##secuencia en assembly que se traduce desde la línea de "C", creemos es mas claro de esta manera.
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
##!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


##//Informacion para el debugger -{
.section .mdebug.abi32
.previous
.abicalls
##//Informacion para el debugger -}


.text ##//Empieza la parte ejecutable.


##==============================================================================
## Function "tp1_heapsort" begin
##==============================================================================
##/*
##Ordenamiento heap.
##
##1er parámetro: Array de palabras.
##
##2do parámetro: Cantidad de palabras.
##
##
##devuelve: -.
##*/


##PARAMETERS

##a0 = char** words	(1 word)
##a1 = int n		(1 word)


##STACK SIZE

##SRA =		3 words + 1 words padd	= 4 words
##FPSRA =	0 words + 0 words padd	= 0 words
##LTA =		5 words + 1 words padd	= 6 words
##ABA =		2 words + 2 words padd	= 4 words

##TOTAL FRAME SIZE = 14 words = 56 Bytes

#######################################################################################

##!!!!! ES NECESARIA UNA VERSION EXTENDIDA DEL STACK PARA PODER USAR GBD. !!!!!

##TOTAL FRAME SIZE = 64 Bytes (en la versión extendida).

##El GDB necesita dos words extra al final del LTA, no hay
##documentación acerca de porque, pero de no estar el GDB
##no se comporta correctamente, solo se utilizó este stack
##"extendido", durante el debugging.
#######################################################################################


##Constantes de definicion del stack frame - {

## FS=Frame Size

##56\64
#define FS		56

##40\48
#define GP		40

##44\52
#define FP		44

##48\56
#define RA		48

##56\64
#define A0		56

##56\64
#define _words		56

##60\68
#define A1		60

##60\68
#define _n		60


##variables locales
##int i = n, j = n/2, parent, child;
##char* t;

##16\24
#define _i		16

##20\28
#define _j		20

##24\32
#define _parent		24

##28\36
#define _child		28

##32\40
#define _t		32


##variables temporales

##----

##GP\(FS-GP)
#define GP_STORE	GP

##Constantes de definicion del stack frame - }

	.align 2		##alineación a 4 bytes.
	.globl tp1_heapsort 	##Funcion pública.
	.ent tp1_heapsort	##Comienzo de la función.
tp1_heapsort:			##
	.frame $fp,FS,ra	##.frame es una pseudo instrucción al preprocesador\ensamblador que le indica
				##el tamaño del bloque de activación (requerido por GCC para código PIC).

###############################
##//Creo el stack frame - {

	.set noreorder		##.cpload es una pseudo instrucción al preprocesador\ensamblador que le indica
	.cpload t9		##como calcular la GOT (global offset table).
	.set reorder		##El noreorder\reorder desactiva el reordenamiento por optimización.
				##
	subu	sp,sp,FS	##"Reservo" el espacio para el stack frame.
	.cprestore GP_STORE	##.cprestore toma como parámetro el offset de donde se guarda gp.
				##
	sw	ra,RA(sp)	##Salvo el registro ra.
	sw	$fp,FP(sp)	##Salvo el registro fp.
	sw	gp,GP(sp)	##Salvo el registro gp.
	move	$fp,sp		##fp apunta al stack frame.
				##
	sw	a0,A0($fp)	##Salvo el registro a0 (1er parámetro).
	sw	a1,A1($fp)	##Salvo el registro a1 (2do parámetro).

##//Creo el stack frame - }
###############################

				## i = n;
	lw	t0,_n($fp)	##
	sw	t0,_i($fp)	##
				## j = n/2;
	lw	t1,_n($fp)	##
##	li	t0,2		## [t0=2]
##	divu	t1,t0		## [<hi(remainder),lo(quotient)>=t1/t0]
##	mflo	t0		## [t0=lo]
	srl	t0,t1,1		## [to=t1/2] //Estoy ignorando el signo, pero n>=0.
	sw	t0,_j($fp)	##
				##
WHL_1:				## while (true) {
				##
				##  if (j > 0) {
	lw	t0,_j($fp)	##
	blez	t0,IF_1		##
				##   t = words[--j];
	addu	t0,t0,-1	##
	sw	t0,_j($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t0,t1,t0	##
	lw	t0,0(t0)	##
	sw	t0,_t($fp)	##
	b	IF_1_E		##  } //if (j > 0)
IF_1:				##  else {
				##
				##   if (--i == 0)
	lw	t0,_i($fp)	##
	addu	t0,t0,-1	##
	sw	t0,_i($fp)	##
	beq	t0,zero,WHL_1_F	##    break;
				##
				##   t = words[i];
	lw	t0,_i($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t0,t1,t0	##
	lw	t0,0(t0)	##
	sw	t0,_t($fp)	##
				##
				##   words[i] = words[0];
	lw	t0,_i($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t1,t1,t0	##
	lw	t0,_words($fp)	##
	lw	t0,0(t0)	##
	sw	t0,0(t1)	##
IF_1_E:				##  } //if (j > 0)
				##
				##  parent = j;
	lw	t0,_j($fp)	##
	sw	t0,_parent($fp)	##
				##  
				##  child = j*2 + 1;
	lw	t0,_j($fp)	##
	sll	t0,t0,1		## [t0=t0*2]
	addu	t0,t0,1		##
	sw	t0,_child($fp)	##
				##
WHL_2:				##  while (child < i) {
				##
	lw	t0,_child($fp)	##
	lw	t1,_i($fp)	##
	slt	t0,t0,t1	##
	beq	t0,zero,WHL_2_F	##
				##
				##   if ((child + 1) < i  &&  (compare_str(words[child + 1], words[child]) > 0)) {
				##
	lw	t0,_child($fp)	##
	addu	t1,t0,1		##
	lw	t0,_i($fp)	##
	slt	t0,t1,t0	##
	beq	t0,zero,IF_3_F	##
	lw	t0,_child($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t0,t1,t0	##
	addu	a0,t0,4		##
	lw	t0,_child($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t0,t1,t0	##
	lw	a0,0(a0)	##
	lw	a1,0(t0)	##
	lw	t9,compare_str	##
	jal	ra,t9		##
	blez	v0,IF_3_F	##
				##
				##    child++;
	lw	t0,_child($fp)	##
	addu	t0,t0,1		##
	sw	t0,_child($fp)	##
IF_3_F:				##   }//if ((child + 1) < i  &&  (compare_str(words[child + 1], words[child]) > 0)) {
				##
				##   if (compare_str(words[child], t) > 0) {
	lw	t0,_child($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t0,t1,t0	##
	lw	a0,0(t0)	##
	lw	a1,_t($fp)	##
	lw	t9,compare_str	##
	jal	ra,t9		##
	blez	v0,WHL_2_F	## [if (V0 <= 0) goto WHL_2_F] //else break;
				##
				##    words[parent] = words[child];
	lw	t0,_parent($fp)	##
	sll	t1,t0,2		##
	lw	t0,_words($fp)	##
	addu	a0,t1,t0	##
	lw	t0,_child($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t0,t1,t0	##
	lw	t0,0(t0)	##
	sw	t0,0(a0)	##
				##    parent = child;
	lw	t0,_child($fp)	##
	sw	t0,_parent($fp)	##
				##    child = parent*2+1;
	lw	t0,_parent($fp)	##
	sll	t0,t0,1		## [t0=t0*2]
	addu	t0,t0,1		##
	sw	t0,_child($fp)	##
	b	WHL_2		## [goto WHL_2]
WHL_2_F:			##  } //while (child < i)
				##
				##  words[parent] = t;
	lw	t0,_parent($fp)	##
	sll	t1,t0,2		## [t1=t0*4]
	lw	t0,_words($fp)	##
	addu	t1,t1,t0	##
	lw	t0,_t($fp)	##
	sw	t0,0(t1)	##
	b	WHL_1		## [goto WHL_1]
WHL_1_F:			## }//while (true)

###############################
##//Destruyo el stack frame - {

	move	sp,$fp		##Reinicio el stack pointer.
	lw	ra,RA(sp)	##Restauro el registro ra.
	lw	$fp,FP(sp)	##Restauro el registro fp.
	addu	sp,sp,FS	##Elimino el lugar reservado para el stack frame.

##//Destruyo el stack frame - }
###############################

	j	ra		##return;


	.end tp1_heapsort
	.size tp1_heapsort, .-tp1_heapsort

##==============================================================================
## Function "tp1_heapsort" end
##==============================================================================

##//Informacion para el debugger -{
	.ident	"Hand compiler 0.9.0 :)"
##//Informacion para el debugger -}



